/*
 * @lc app=leetcode.cn id=148 lang=cpp
 *
 * [148] 排序链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
 public:
  /*ListNode* sortList(ListNode* head) {
  current = dummy.next;
  tail = dummy;
  for(step=1;step<length;step*=2)
  {
    // left->@->@->@->@->@->@->null
    left = current;
    // left->@->@->null   right->@->@->@->@->null
    right=cut(current,step); // 将 current 切掉前 step 个头切下来。
    // left->@->@->null   right->@->@->null   current->@->@->null
    current=cut(right, step); // 将 right 切掉前 step 个头切下来。
    // dummy.next -> @->@->@->@->null，最后一个节点是 tail，始终记录
                //                        ^
                //                        tail
    tail.next = merge(left, right);
    while(tail->next) tail=tail->next; // 保持tial为尾部

  }
  }*/

  ListNode* sortList(ListNode* head)
  {
    int n = 0;
    for (auto p = head; p; p = p->next) n++;

    auto dummy = new ListNode(-1);
    dummy->next = head;

    // 以2i为单位切片cut
    // 从前往后搜秒长度为2i的段
    for (int i = 1; i < n; i *= 2)
    {
      auto cur = dummy;
      // 枚举每2i段
      for (int j = 0; j + 1 < n; j += i * 2)
      {
        // 每次第一段(左边这一段left)
        auto left = cur->next, right = cur->next;
        // right要往后枚举i步
        for (int k = 0; k < i; k++) right = right->next;
        // 长度为i的归并排序，从i=1开始，自底向上
        // l是左边循环的长度，r是右边的长度，两边长度都为i
        int l = 0, r = 0;
        while (l < i && r < i && right)  // right为防止最后一段长度不全的情况
          // 经典的归并过程
          if (left->val <= right->val)  // left排在前
          {
            cur->next = left;  // left放到当前位置下一个节点
            cur = left;
            left = left->next;
            l++;
          }
          else
          {
            cur->next = right;
            cur = right;
            right = right->next;
            r++;
          }

        // 最后把左右两段长度为i接起来,不需要归并了，直接接
        // r段已经归并完，剩下的全为l段，因此直接添加到cur的后面
        while (l < i)
        {
          cur->next = left;
          cur = left;
          left = left->next;
          l++;
        }
        while (r < i && right)
        {
          cur->next = right;
          cur = right;
          right = right->next;
          r++;
        }

        cur->next = right;
      }
    }
    return dummy->next;
  }
};
// @lc code=end
